﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;
using alib.Debugging;

using alib.Hashing;
using alib.Enumerable;
using alib.Collections;
using alib.Array;

namespace alib.dg
{
	using String = System.String;
	using Enumerable = System.Linq.Enumerable;
	using Array = System.Array;
	using AlibArr = alib.Array.arr;

	public abstract partial class dg : IGraph
	{
#if DEBUG
		[DebuggerBrowsable(DebuggerBrowsableState.Never)]
		public static IGraph _singleton;
#endif

		[DebuggerBrowsable(DebuggerBrowsableState.Never)]
		public static readonly Eref[] NoErefs = Collection<Eref>.None;
		[DebuggerBrowsable(DebuggerBrowsableState.Never)]
		public static readonly Vref[] NoVrefs = Collection<Vref>.None;
		[DebuggerBrowsable(DebuggerBrowsableState.Never)]
		public static readonly Edge[] NoEdges = Collection<Edge>.None;
		[DebuggerBrowsable(DebuggerBrowsableState.Never)]
		public static readonly Vertex[] NoVerticies = Collection<Vertex>.None;

		public dg(Edge[] E, Vertex[] V)
		{
#if DEBUG
			if (this is IStringGraph)
				_singleton = (IStringGraph)this;
#endif
			this.E = E ?? NoEdges;
			this.c_edge_max = this.E.Length;
			this.c_edge_free = 0;

			this.V = V ?? NoVerticies;
			this.c_vertex_max = this.V.Length;
			this.c_vertex_free = 0;
		}
		public dg()
			: this(default(Edge[]), default(Vertex[]))
		{
		}
		public dg(dg to_copy)
			: this(to_copy.E, to_copy.V)
		{
			this.c_edge_max = to_copy.c_edge_max;
			this.c_edge_free = to_copy.c_edge_free;

			this.c_vertex_max = to_copy.c_vertex_max;
			this.c_vertex_free = to_copy.c_vertex_free;
		}

		public Vertex[] V;
		protected int c_vertex_max;
		public int c_vertex_free;
		public int VertexAlloc { [DebuggerStepThrough] get { return c_vertex_max; } }
		public int VertexCount { [DebuggerStepThrough] get { return c_vertex_max - c_vertex_free; } }
		public Vertex[] Verticies { get { return V; } }
		public virtual String vertex_string(Vref vr) { return V[vr].value.ToString(); }

		public Edge[] E;
		protected int c_edge_max;
		public int c_edge_free;
		public int EdgeAlloc { [DebuggerStepThrough] get { return c_edge_max; } }
		public int EdgeCount { [DebuggerStepThrough] get { return c_edge_max - c_edge_free; } }
		public Edge[] Edges { get { return E; } }
		public virtual String edge_string(Eref er) { return E[er].value.ToString(); }

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// VERTICIES
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

		[DebuggerStepThrough]
		public bool vertex_is_valid(Vref vr) { return vr >= 0 && vr < VertexAlloc && !V[vr].IsFree; }

		[DebuggerStepThrough]
		public int vertex_value(Vref v) { return V[v].value; }

		[DebuggerStepThrough]
		public Eref vertex_first_edge(Vref v) { return V[v].e_out; }

		[DebuggerStepThrough]
		public int vertex_out_edge_count(Vref v) { return V[v].c_out; }

		public int vertex_in_edge_count(Vref v)
		{
			var e = V[v].e_in;
			if (e < 0)
				return 0;
			return edge_peer_count(e);
		}

		[DebuggerStepThrough]
		public Eref[] vertex_in_edges(Vref v)
		{
			var e = V[v].e_in;
			return e < 0 ? NoErefs : edge_peers(e);
		}

		public Eref vertex_unary_parent(Vref v)
		{
			var e = V[v].e_in;
			return e < 0 || E[e].e_next != e ? Eref.NotValid : e;
		}

		[DebuggerStepThrough]
		public bool vertex_is_leaf(Vref v) { return V[v].c_out == 0; }

		[DebuggerStepThrough]
		public bool vertex_is_top(Vref v) { return V[v].e_in == Eref.None; }

		public bool vertex_has_edge_to(Vref v, Vref v_to)
		{
			int c = V[v].c_out;
			if (c > 0)
				for (Eref e = V[v].e_out, e_last = e + c; e < e_last; e++)
					if (E[e].v_to == v_to)
						return true;
			return false;
		}

		public unsafe bool vertex_has_ancestor(Vref v_upper, Vref v_lower)
		{
			int cb = ((VertexAlloc - 1) >> 6) + 1;
			ulong* pul = stackalloc ulong[cb];
			var ba = new alib.Bits.BitHelper(pul, cb);
			_mark_ancestors(v_lower, ref ba);
			return ba[v_upper];
		}

		[DebuggerStepThrough]
		public Eref[] vertex_out_edges(Vref v) { return V[v].out_edges; }

		public int[] vertex_out_values(Vref v)
		{
			int c;
			if ((c = V[v].c_out) == 0)
				return Collection<int>.None;

			var arr = new int[c];
			var e = V[v].e_out;
			for (int i = 0; i < c; i++, e++)
				arr[i] = E[e].value;
			return arr;
		}

		[DebuggerStepThrough]
		public Eref vertex_master_edge(Vref v) { return V[v].e_in; }

		[DebuggerStepThrough]
		public bool vertex_is_coreferenced(Vref v) { return edge_target_coreferenced(V[v].e_in); }

		public void vertex_switch_master_edge(Vref v, Eref e_new)
		{
			var e_old = V[v].e_in;
			if (e_old >= 0 && e_old != e_new)
			{
				if (!edge_has_peer(e_old, e_new))
					throw new Exception();
				V[v].e_in = e_new;
			}
		}

		public Vref[] vertex_parents(Vref v)
		{
			Eref e = V[v].e_in;
			if (e == Eref.None)
				return NoVrefs;

			int c = edge_peer_count(e);
			if (c == 1)
				return new[] { E[e].v_from };

			var arr = new Vref[c];
			while (--c >= 0)
			{
				arr[c] = E[e].v_from;
				e = E[e].e_next;
			}
			return arr;
		}
#if true
		//public Vref[] vertex_parents_distinct(Vref v)
		//{
		//	var a = vertex_parents_distinct1(v);
		//	var b = vertex_parents_distinct2(v);

		//	Array.Sort(a);
		//	Array.Sort(b);
		//	if (!a.SequenceEqual(b))
		//	{
		//		throw new Exception();
		//	}
		//	return a;
		//}

		public Vref[] vertex_parents_distinct(Vref v)
		{
			Eref e;
			if ((e = V[v].e_in) == Eref.None)
				return NoVrefs;

			int c = edge_peer_count(e);
			if (c == 1)
				return new[] { E[e].v_from };

			var arr = new Vref[c];
			c = 0;
			var e_start = e;
			do
			{
				v = E[e].v_from;
				for (int j = 0; j < c; j++)
					if (arr[j] == v)
						goto already_have;
				arr[c++] = v;
			already_have:
				;
			}
			while ((e = E[e].e_next) != e_start);

			if (c < arr.Length)
				arr = AlibArr.Resize(arr, c);
			return arr;
		}
#else
		public Vref[] vertex_parents_distinct(Vref v)
		{
			Eref e;
			if ((e = V[v].e_in) == Eref.None)
				return NoVrefs;

			int c = edge_peer_count(e);
			var arr = new Vref[c];
			arr[0] = E[e].v_from;

			if (c > 1 && c > (c = _vpd(e, arr)))
				arr = AlibArr.Resize(arr, c);

			return arr;
		}

		int _vpd(Eref e, Vref[] arr)
		{
			var e_start = e;
			var v = arr[0];
			int j, c = 1;
			while ((e = E[e].e_next) != e_start)
			{
				if (v == (v = E[e].v_from))
					continue;
				for (j = c - 1; j >= 0; j--)
					if (arr[j] == v)
						goto already_have;
				arr[c++] = v;
			already_have:
				;
			}
			return c;
		}
#endif

		public int vertex_vref_parent_count(Vref v, Vref par)
		{
			Nop.Untested();
			Eref e;
			int c = 0;
			if ((e = V[v].e_in) >= 0)
			{
				Eref e_start = e;
				do
					if (E[e].v_from == par)
						c++;
				while ((e = E[e].e_next) != e_start);
			}
			return c;
		}

		public unsafe Vref[] vertex_ancestors(Vref v)
		{
			if (V[v].e_in == Eref.None)
				return NoVrefs;

			int cb = ((VertexAlloc - 1) >> 6) + 1;
			ulong* pul = stackalloc ulong[cb];
			var ba = new alib.Bits.BitHelper(pul, cb);

			return _from_bitarray(_mark_ancestors(v, ref ba), ref ba);
		}

		public unsafe Vref[] vertex_ancestors_and_self(Vref v)
		{
			if (V[v].e_in == Eref.None)
				return new[] { v };

			int cb = ((VertexAlloc - 1) >> 6) + 1;
			ulong* pul = stackalloc ulong[cb];
			var ba = new alib.Bits.BitHelper(pul, cb);

			ba[v] = true;
			return _from_bitarray(_mark_ancestors(v, ref ba) + 1, ref ba);
		}

		public Vref[] vertex_children(Vref v)
		{
			int c = V[v].c_out;
			if (c == 0)
				return NoVrefs;

			var arr = new Vref[c];
			Eref e = V[v].e_out;
			for (int i = 0; i < c; i++, e++)
				arr[i] = E[e].v_to;
			return arr;
		}

		public Vref[] vertex_children_distinct(Vref v)
		{
			int i, j, c;

			if ((c = V[v].c_out) == 0)
				return NoVrefs;
			Eref e = V[v].e_out;
			if (c == 1)
				return new[] { E[e].v_to };

			var arr = new Vref[c];
			for (c = i = 0; i < arr.Length; i++)
			{
				v = E[e + i].v_to;
				for (j = 0; j < c; j++)
					if (arr[j] == v)
						goto already_have;
				arr[c++] = v;
			already_have:
				;
			}
			if (c < arr.Length)
				arr = AlibArr.Resize(arr, c);
			return arr;
		}

		public Eref[] vertex_cotargeted_edges(Vref v)
		{
			int c;

			if ((c = V[v].c_out) < 2)
				return NoErefs;

			//int c = VertexAlloc;
			//for (Vref v = Vref.Zero; v < c; v++)
			//	if (vertex_is_valid(v) && !vertex_children(v).IsDistinct())
			//		return true;
			//return false;
			throw new NotImplementedException();
		}

		public unsafe Vref[] vertex_descendants(Vref v)
		{
			if (V[v].c_out == 0)
				return NoVrefs;

			int cb = ((VertexAlloc - 1) >> 6) + 1;
			ulong* pul = stackalloc ulong[cb];
			var ba = new alib.Bits.BitHelper(pul, cb);

			return _from_bitarray(_mark_descendants(v, ref ba), ref ba);
		}

		public unsafe Vref[] vertex_descendants_and_self(Vref v)
		{
			int c = V[v].c_out;
			if (c == 0)
				return new[] { v };

			int cb = ((VertexAlloc - 1) >> 6) + 1;
			ulong* pul = stackalloc ulong[cb];
			var ba = new alib.Bits.BitHelper(pul, cb);

			ba[v] = true;
			return _from_bitarray(_mark_descendants(v, ref ba) + 1, ref ba);
		}


		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// EDGES
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

		[DebuggerStepThrough]
		public bool edge_is_valid(Eref er) { return er >= 0 && er < EdgeAlloc && !E[er].IsFree; }

		[DebuggerStepThrough]
		public Vref edge_parent(Eref e) { return E[e].v_from; }

		[DebuggerStepThrough]
		public Eref edge_next_peer(Eref e) { return E[e].e_next; }

		[DebuggerStepThrough]
		public int edge_value(Eref e) { return E[e].value; }

		[DebuggerStepThrough]
		public Vref edge_target(Eref e) { return E[e].v_to; }

		[DebuggerStepThrough]
		public bool edge_target_coreferenced(Eref e) { return e != E[e].e_next; }

		[DebuggerStepThrough]
		public bool edge_is_non_coref_or_master(Eref e) { return e == V[E[e].v_to].e_in; }
		[DebuggerStepThrough]
		public bool edge_is_master(Eref e) /*  same   */{ return e == V[E[e].v_to].e_in; }

		public void edge_set_master(Eref e) { vertex_switch_master_edge(E[e].v_to, e); }

		public bool edge_is_coref_and_master(Eref e) { return e != E[e].e_next && e == V[E[e].v_to].e_in; }

		public Eref get_edge(Vref v_from, Vref v_to)
		{
			int c = V[v_from].c_out;
			if (c > 0)
				for (Eref e = V[v_from].e_out, e_end = e + c; e < e_end; e++)
					if (E[e].v_to == v_to)
						return e;
			return Eref.NotValid;
		}

		public int edge_peer_count(Eref e)
		{
			if (e < 0)
				return 0;
			int c = 1;
			var i = e;
			while ((i = E[i].e_next) != e)
				c++;
			return c;
		}

		public Eref edge_peer_list_prev(Eref e)
		{
			Eref tmp, cur = e;
			while (e != (tmp = E[cur].e_next))
				if (e == (cur = E[tmp].e_next))
					return tmp;
			return cur;
		}

		public bool edge_has_peer(Eref e, Eref e_unk)
		{
			if (e_unk < 0 || e < 0)
				return false;

			var i = e;
			do
				if (i == e_unk)
					return true;
			while ((i = E[i].e_next) != e);
			return false;
		}

		public Eref[] edge_peers(Eref e)
		{
			int c = edge_peer_count(e);
			if (c == 0)
				return NoErefs;
			if (c == 1)
				return new[] { e };

			var arr = new Eref[c];
			while (--c >= 0)
				arr[c] = e = E[e].e_next;

			return arr;
		}

		public IEnumerable<int[]> edge_paths(Eref e)
		{
			Edge ee;
			if (e < 0)
				yield return Collection<int>.None;
			else
				foreach (var e_back in edge_peers(e))
					foreach (var q in edge_paths(V[(ee = E[e_back]).v_from].e_in))
						yield return q.Append(ee.value);
		}

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// GRAPH
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

		[DebuggerBrowsable(DebuggerBrowsableState.Never)]
		public Vref[] verticies
		{
			get
			{
				var arr = new Vref[VertexCount];
				int i = 0;
				for (Vref vr = Vref.Zero; i < arr.Length; vr++)
					if (vertex_is_valid(vr))
						arr[i++] = vr;
				Debug.Assert(i == VertexCount);
				return arr;
			}
		}

		[DebuggerBrowsable(DebuggerBrowsableState.Never)]
		public IReadOnlyCollection<Eref> edges
		{
			get
			{
				var arr = new Eref[EdgeCount];
				int i = 0;
				for (Eref er = Eref.Zero; i < arr.Length; er++)
					if (edge_is_valid(er))
						arr[i++] = er;
				Debug.Assert(i == EdgeCount);
				return arr;
			}
		}

		[DebuggerBrowsable(DebuggerBrowsableState.Never)]
		public IEnumerable<Vref> tops
		{
			get
			{
				int c = VertexAlloc;
				for (Vref v = Vref.Zero; v < c; v++)
					if (vertex_is_valid(v) && V[v].e_in == Eref.None)
						yield return v;
			}
		}

		[DebuggerBrowsable(DebuggerBrowsableState.Never)]
		public IEnumerable<Vref> leaves
		{
			get
			{
				Vref v = Vref.Zero;
				int c;
				do
				{
					c = VertexAlloc;
					for (; v < c; v++)
						if (vertex_is_valid(v) && V[v].c_out == 0)
							yield return v;
				}
				while (c < VertexAlloc);
			}
		}

		//public bool has_duplicate_edges()
		//{
		//	int c = VertexAlloc;
		//	for (Vref v = Vref.Zero; v < c; v++)
		//		if (vertex_is_valid(v) && !vertex_children(v).IsDistinct())
		//			return true;
		//	return false;
		//}

		public Vref[][] GetVertexLevelGroups()
		{
			var fl = new _find_levels(this);
			var levels = fl.levels;
			int cv = levels.Length, c_levels = fl.max_level + 1;

			Vref[][] grps = new Vref[c_levels][];
			for (int i = 0; i < cv; i++)
			{
				int vl = levels[i];
				alib.Array.arr.Append(ref grps[vl], (Vref)i);
			}
			Debug.Assert(grps.Sum(x => x.Length) == VertexCount);
			return grps;
		}

		public int[] GetVertexLevels() { return new _find_levels(this).levels; }

		////////////////////////////////////////////////////////////
		/// 
		struct _find_levels
		{
			public _find_levels(dg graph)
			{
				this.graph = graph;
				this.max_level = 0;
				int c = graph.VertexAlloc;
				this.levels = new int[c];
				for (int i = 0; i < c; i++)
				{
					if (graph.V[i].c_out == 0)
						get_level((Vref)i);
				}
			}

			readonly dg graph;
			public readonly int[] levels;
			public int max_level;

			int get_level(Vref v)
			{
				int pl, lev = levels[v];
				Eref e;
				if (lev == 0 && (e = graph.V[v].e_in) != Eref.None)
				{
					var arr = graph.vertex_in_edges(v);
					for (int i = 0; i < arr.Length; i++)
						if ((pl = get_level(graph.edge_parent(arr[i]))) > lev)
							lev = pl;
					if ((levels[v] = ++lev) > max_level)
						max_level = lev;
				}
				return lev;
			}
		};
		/// 
		////////////////////////////////////////////////////////////


		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// non-public
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

		protected unsafe int _mark_ancestors(Vref vr, ref alib.Bits.BitHelper ba)
		{
			var rgp = vertex_parents(vr);
			int c = 0, c_par = rgp.Length;
			Vref par;
			for (int j = 0; j < c_par; j++)
				if (!ba[par = rgp[j]])
				{
					ba[par] = true;
					c += _mark_ancestors(par, ref ba) + 1;
				}
			return c;
		}

		protected int _mark_descendants(Vref vr, ref alib.Bits.BitHelper ba)
		{
			var rgc = vertex_children(vr);
			int c = 0, cc = rgc.Length;
			Vref child;
			for (int j = 0; j < cc; j++)
				if (!ba[child = rgc[j]])
				{
					ba[child] = true;
					c += _mark_descendants(child, ref  ba) + 1;
				}
			return c;
		}

		Vref[] _from_bitarray(int c, ref alib.Bits.BitHelper ba)
		{
			var ret = new Vref[c];
			for (int i = 0, j = 0; j < c; i++)
				if (ba[i])
					ret[j++] = new Vref(i);
			return ret;
		}

		public override String ToString()
		{
			return String.Format("edges: {0}/{1}  verticies:{2}/{3}", EdgeCount, EdgeAlloc, VertexCount, VertexAlloc);
		}

	};
}
